﻿// Dijsktra.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
using namespace std;

//1. 找离Start最近的点
//2. 获取到start最短路径
//3.以这个最近点为起始点，继续找最近的点
//4.获取到start的最短路径
#define INFINITE 99999

#define PointCount   6
//地图
int graph[PointCount][PointCount];
//
struct GraphDist
{
	int startId;
	int enndId;
	int dist;
};

struct GraphPoint
{
	int id{ -1 };			//当前点的ID
	bool bVisit{ false };	//是否已经访问过
	GraphPoint(int ID, bool b)
	{
		id = ID;
		bVisit = b;
	}
};


void InitGraph()
{
	for (int h = 0; h < PointCount; h++)
	{
		for (int w = 0; w < PointCount; w++)
		{
			graph[w][h] = INFINITE;
		}
	}
	/*graph[0][0] = 0;
	graph[1][0] = 1;
	graph[2][0] = 12;

	graph[1][1] = 0;
	graph[2][1] = 9;
	graph[3][1] = 3;

	graph[2][2] = 0;
	graph[4][2] = 5;

	graph[2][3] = 4;
	graph[3][3] = 0;
	graph[4][3] = 13;
	graph[5][3] = 15;

	graph[4][4] = 0;
	graph[5][4] = 4;

	graph[5][5] = 0;*/
	graph[0][2] = 10;
	graph[0][4] = 30;
	graph[0][5] = 100;

	graph[1][2] = 5;

	graph[2][3] = 50;

	graph[3][5] = 10;
	
	graph[4][3] = 20;
	graph[4][5] = 60;


}

int main()
{
	int startPointId = 0;
	int destPointId = 5;
	InitGraph();
	bool bVisit[PointCount];	//当前节点是否被记录在前驱节点
	for (int i = 0; i < PointCount; i++)
	{
		bVisit[i] = false;
	}
	//vector<int> path;	//表示路径
	int prev[PointCount];
	int dst[PointCount];
	for (int i = 0; i < PointCount; i++)
	{
		prev[i] = startPointId;
		dst[i] = graph[startPointId][i];	//起始点到该点的距离
	}
	bVisit[startPointId] = true;

	int minPointId = startPointId;	//最近的点的ID
	for (int k = 0; k < PointCount - 1; k++)
	{
		int minDist = INFINITE;	//最近的点的距离
		for (int i = 0; i < PointCount; i++)
		{
			if (!bVisit[i] && minDist > dst[i])
			{
				minPointId = i;
				minDist = dst[i];
			}
		}
		//第二个点是minPointID
		//prev[startPointId] = minPointId;
		bVisit[minPointId] = true;
		int dis;
		for (int i = 0; i < PointCount; i++)
		{
			dis = graph[minPointId][i] == INFINITE ? INFINITE : minDist + graph[minPointId][i];
			if (!bVisit[i] && dst[i] > dis)
			{
				dst[i] = dis;
				prev[i] = minPointId;
			}
		}
	}
	//打印路径
	int p = destPointId;
	while ( p != startPointId )
	{
		cout << prev[p]+1 << "->";
		p = prev[p];
	}
	//int p = startPointId;
	//for (int i = 0; i < PointCount; i++)
	//{
	//	cout<<
	//	/*cout << prev[p] << "->";
	//	p = prev[p];*/
	//}

//	cout << startPointId+1;


	std::cout << "Hello World!\n";
}

